package K次取反后最大化的数组和;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author: AirMan
 * @date: 2025/4/23 10:14
 * @description:
 */
public class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // greedy
        // 每次都找负数最小的数进行反转，如果nums全为正，那么我们每次找整数最小的数进行反转
        // 局部最优：每次都是反转的最负数，每次带来的收益最大
        // 全局最优：每次带来的收益最大 ==> 整体就是一个最大和

        Arrays.sort(nums); // 从小到大排序，最小的负数一定在前面
        for (int i = 0; i < nums.length && k > 0; i++) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        // 如果 k 仍然不为0。寻找当前的最小整数，利用它进行反复消耗，每次操作带来的损失都是最小的
        if (k % 2 == 1) {
            Arrays.sort(nums);
            nums[0] = -nums[0];
        }
        // k > 0 && k is even，flip数字不会产生影响: 对于负数: 负-正-负；对于正数：正-负-正
        return Arrays.stream(nums).sum();
    }
}
